#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> stack;
        vector<int> re;
        re = nums;
        
        stack.push_back(0);
        for (int i = 1, j = 1; j < nums.size() * 2 - 1; j++) {
        /*for (int i = 1, j = i - 1; i != j; ) {*/
            while (!stack.empty() && nums[i] > nums[stack.back()])
            {
                /*int idx = stack.back();*/
                re[stack.back()] = nums[i];
                // re[i] = stack.back();
                stack.pop_back();
            }
            stack.push_back(i);
            // re[i] = nums[i];
            i = (i + 1)  % nums.size();
            /*j = (i - 1) % nums.size();*/
        }
        for (int i = 0; i < nums.size(); i++) {
            if (re[i] == nums[i])
                re[i] = -1;
        }
        return re;
    }
};

void test01() {
    vector<int> input = {1, 2, 1};
    Solution obj;

    vector<int> re = obj.nextGreaterElements(input);
    for (auto item : re) {
        cout << item << " ";
    }
    cout << endl;
}

void test02() {
    vector<int> input = {1, 2, 3, 4, 3};
    Solution obj;

    vector<int> re = obj.nextGreaterElements(input);
    for (auto item : re) {
        cout << item << " ";
    }
    cout << endl;
}

void test03() {
    vector<int> input = {1, 2, 3, 4, 5};
    // 预期结果 [2,3,4,5,-1]
    Solution obj;

    vector<int> re = obj.nextGreaterElements(input);
    for (auto item : re) {
        cout << item << " ";
    }
    cout << endl;
}

void test04() {
    vector<int> input = {0};
    // 预期结果 [-1]
    Solution obj;

    vector<int> re = obj.nextGreaterElements(input);
    for (auto item : re) {
        cout << item << " ";
    }
    cout << endl;
}

void test05() {
    vector<int> input = {1, 1, 1};
    // 预期结果 [-1, -1, -1]
    Solution obj;

    vector<int> re = obj.nextGreaterElements(input);
    for (auto item : re) {
        cout << item << " ";
    }
    cout << endl;
}

void test06() {
    vector<int> input = {-1, 0};
    // 预期结果 [0, -1]
    Solution obj;

    vector<int> re = obj.nextGreaterElements(input);
    for (auto item : re) {
        cout << item << " ";
    }
    cout << endl;
}

int main() {
    std::cout << "this is Leetcode-503-demo." << std::endl;
    std::cout << "test01:" << std::endl;
    test01();

    std::cout << "test02:" << std::endl;
    test02();

    std::cout << "test03:" << std::endl;
    test03();

    std::cout << "test04:" << std::endl;
    test04();

    std::cout << "test05:" << std::endl;
    test05();

    std::cout << "test06:" << std::endl;
    test06();
    return 0;
}
